// 给定一个全部由小写字母组成的字符串S，重复的删除相邻且相同的字母，直到相邻字母不再有相同的

// 思路： 堆栈，用栈存储不重复的字符，用top元素和当前遍历元素比较，如果相同则把出栈，知道遍历结束
// 时间复杂度：O(n)，n是字符串的长度
// 空间复杂度：O(n)，stack的大小

function removeDuplicates(str) {
    let stack = []
    for (let i = 0; i < str.length; i++) {
        if (stack.length && stack[stack.length - 1] === str[i]) {
            stack.pop()
        } else {
            stack.push(str[i])
        }
    }
    return stack.join('')
}

let S = "abbaca"
console.log(removeDuplicates(S))